package leetcode.剑指offer.后40;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/1 22:08
 * @description：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */
public class 剑指_51_数组中的逆序对 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.reversePairs(new int[]{7, 5, 6, 4}));
    }

    /**
     * 暴力
     */
    class Solution {
        public int reversePairs(int[] nums) {
            if (nums.length < 2) return 0;
            int count = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            map.put(nums[nums.length - 1], 0);
            for (int i = nums.length - 2; i >= 0; i--) {
                int cur = nums[i];
                int j = i + 1;
                while (cur < nums[j]) {
                    j++;
                }
                if (j == nums.length) {
                    map.put(cur, 0);
                    continue;
                }
                count += map.get(nums[j]) + 1;
                map.put(cur, map.get(nums[j]) + 1);
            }
            System.out.println(Collections.unmodifiableMap(map));
            return count;
        }
    }
}
